package main

import "math"

// O(log^2C), C = range of 32-bit integers; O(1)
func divide(dividend int, divisor int) int {
	ret := 0
	if dividend == 0 {
		return ret
	}
	if dividend == math.MinInt32 {
		if divisor == 1 {
			return math.MinInt32
		}
		if divisor == -1 {
			return math.MaxInt32
		}
	}
	if dividend == math.MaxInt32 {
		if divisor == 1 {
			return math.MaxInt32
		}
		if divisor == -1 {
			return -math.MaxInt32
		}
	}
	if divisor == math.MinInt32 {
		if dividend == math.MinInt32 {
			return 1
		}
		return 0
	}

	// 商的正负
	var pos bool = (dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0)

	// 将两者变为同号方便计算，如果都变正数，则可能溢出；因此全变成负数
	if dividend > 0 {
		dividend = -dividend
	}
	if divisor > 0 {
		divisor = -divisor
	}

	// Binary search
	left, right := 1, math.MaxInt32
	for left <= right {
		mid := left + (right-left)>>1 // 用移位操作代替除法
		if quickAdd(divisor, mid, dividend) {
			ret = mid
			if mid == math.MaxInt32 { // 注意溢出
				break
			}
			left = mid + 1
		} else {
			right = mid - 1
		}
	}

	if !pos {
		return -ret
	}
	return ret
}

// O(logC)
func quickAdd(y, z, x int) bool {
	for result, add := 0, y; z > 0; z >>= 1 { // 不能使用除法
		if z&1 > 0 {
			// 需要保证 result + add >= x
			if result < x-add {
				return false
			}
			result += add
		}
		if z != 1 {
			// 需要保证 add + add >= x
			if add < x-add {
				return false
			}
			add += add
		}
	}
	return true
}
